#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = -1u >> 2;


struct State {
    int node, stepMod, cost;

    bool operator<(const State &rhs) const {
        return cost > rhs.cost;
    }
};

struct Edge {
    int to;
    int openAt;
};

// 邻接表
vector<vector<Edge> > edges;
vector<vector<int> > dist;
vector<vector<bool> > visited;

int main() {
    int n, m, k;
    int u, v, a;
    cin >> n >> m >> k;
    edges.resize(n);
    dist.resize(n);
    visited.resize(n);
    for (int i = 0; i < n; i++) {
        dist[i].resize(105, INF);
        visited[i].resize(105, false);
    }
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> a;
        edges[u - 1].push_back({v, a});
    }

    priority_queue<State> pq;
    pq.push({0, 0, dist[0][0] = 0});
    while (!pq.empty()) {
        // 拿数据
        int from = pq.top().node, modStep = pq.top().stepMod;
        pq.pop();
        // 判断是否访问过
        if (visited[from][modStep]) continue;
        visited[from][modStep] = true;
        // 从邻接表找邻居
        for (auto edge: edges[from]) {
            // passed: 经过多少路 mod: 到此处步数对k取余
            int passed = dist[from][modStep], currStep = (modStep + 1) % k;
            // 多等一轮
            if (passed < edge.openAt) passed += (edge.openAt - passed + k - 1) / k * k;
            if (dist[edge.to - 1][currStep] > passed + 1)
                pq.push({
                    edge.to - 1, currStep, dist[edge.to - 1][currStep] = passed + 1
                });
        }
    }
    if (dist[n - 1][0] == INF) dist[n - 1][0] = -1;
    cout << dist[n - 1][0] << endl;
    return 0;
}
